\section{Explicación del algoritmo}

Para la resolución del problema se utilizo la técnica de Backtracking. 
Debemos encontrar $k$ conjuntos de vértices(es posible que haya vacios) dentro del grafo
que sumando todos los ejes inter-conjunto(que conectan vértices dentro del mismo
conjunto) tenga el menor peso total. Como no hay forma de a priori saber
cual es el par de vértices que me conviene tener en el mismo conjunto, y que
me garantizaran ser la mejor elección, debemos probar todas las combinaciones.\\

\emph{Por que no puedo saber a priori que par de vértices 
me conviene tener en el mismo conjunto?}\\

Supongamos que los vértices $v1$ y $v2$ se encuentran conectados
por un eje de peso 2 y los vértices $v1$ y $v3$ se encuentran conectados por un
eje de peso 3. Entonces pareciera que si tengo que optar por que par de
vértices ubico en el mismo conjunto, el eje $v1-v2$ es el de menor valor por 
lo tanto al tener $v1$ y $v3$ en conjuntos distintos no sumo el peso 3 de 
ese eje. 
Lo que se omite en este razonamiento es que puede haber mas vértices y 
en ese caso la decisión se complica dado que podría existir un cuarto vértice 
en el conjunto de los vértices $v1,v2$ que este conectado con ambos. Esto
haría que el conjunto $v1,v2,v4$ tenga 3 ejes y mayor costo que la solución 
que planteaba los conjuntos $v1,v3,v4$ y $v2$. 
Lo que se quiere decir es que cualquier análisis de peso de la solución 
antes de conocer el resultado final de las particiones sera en vano
dado que al ir ubicando vértices en distintos conjuntos empiezan a tenerse
en cuenta ejes que antes no se sumaban por no contener a los 2 vértices dentro
del mismo conjunto.
\\
Como se explico anteriormente no hay forma de saber
en un momento dado(en la construcción de una solución al problema), 
si ubicar un vértice en una partición u otra es la mejor decisión, lo 
que se hace es dada una solución probar todas las posibilidades
con los parámetros disponibles.
Así, si cuento con una solución
que ya posee $k$ particiones y dispongo de $T$ vértices aun no
ubicados en ninguna de las particiones lo que deberé hacer
es por cada uno de los vértices disponibles tomarlo y 
probar ubicarlo en cada una de las $k$ particiones. Una vez
ubicado el vértice actual en la partición, tratare de resolver el subproblema
de ubicar los $T-1$ vértices restantes de manera optima. El resultado 
del subproblema sera influenciado por la partición en la que ubique al vértice, de esta manera ire evaluando cual de las decisiones genera un mejor resultado
global en base al subproblema resuelto.

La función que resolverá el problema es recursiva 
y en cada llamada se plantea un problema similar pero con menos vértices aun no ubicados en ninguna partición, y 0 o 1 partición mas que la solución recibida. \\
En el comienzo no hay particiones y ningún vértice aun fue ubicado por lo tanto 
todos son disponibles. Se tomara un vértice y se creara una partición para este, luego con los $n-1$ y la partición creada se llamara recursivamente para poder resolver el subproblema. Este subproblema arrojara un resultado mínimo que nos permitirá evaluar si 
ubicar ese vértice primero en una partición fue lo optimo al compararlo con 
el resultado de colocar primero otro vértice. Entonces en cada paso recibiremos una
solución a medio construir y probaremos todas las combinaciones de vértices con particiones
llamando recursivamente con los subproblemas que eso generara. El mejor resultado
de entre los subproblemas sera el retornado. Cada llamada retornara
el resultado optimo para el subproblema que se plantea. Y así 
en ultima instancia se resolverá el problema completo como la mejor 
combinación de decisiones que me lleva  a un mínimo peso de las particiones.


\section{Pseudocódigo}
\begin{algorithm}[H]
\KwData{EXACTO(R,C)}
- sea R una solucion con I particiones\\
- sea C la  lista de vertices todabia no ubicados en alguna particion \\
- MinRes  mejor solucion conocida \\
- MinV  peso mejor solucion conocida \\
MinV  $\leftarrow$ NULL\\
MinRes  $\leftarrow$ NULL\\
	\While{para cada v  en C}{

		C' $\leftarrow$  C  \backslash \{v\} \\

	    \IF{I$<$K}{\\
		    \tab R' $\leftarrow$  \{v\} \cup R\\
		    \tab ACTUALIZAR\_PESO(R',C')\\
		    \tab T $\leftarrow$ EXACTO(R',C')\\
		    
		    \tab\IF{ MinV = NULL o T$<$MinV  }{\\
		    	\tab\tab   MinRes $\leftarrow$   R'\\
		    	\tab\tab   MinV $\leftarrow$   T\\
		    \tab}
	    }\\
	    \FORALL{ particion P \in  R}{\\
			\tab R' $\leftarrow$   R.insert(P,v)\\ 
			\tab ACTUALIZAR\_PESO(R',C')\\
		    \tab T $\leftarrow$ EXACTO(R',C')\\
		    \tab\IF{ MinV = NULL o T$<$MinV  }{\\
			    	\tab\tab   MinRes $\leftarrow$   R'\\
			    	\tab\tab   MinV $\leftarrow$   T\\
		    \tab}

	    }

	}\\
	\RETURN{Minv}	
\caption{EXACTO()}
\label{alg:ej5}
\end{algorithm}

El pseudocodigo presentado esta simplificado ya que no  posee la poda implementada en la cual si al momento de realizar el cálculo de peso de las lineas 11 y 19 se sobrepasa el valor de $MinV$ no
se hara la llamada recursiva a $EXACTO$. \\

El loop de la linea 7 tratará de ubicar  cada vértice disponible
en una partición nueva o una existente. Luego calculara como 
eso afecta el peso de la solución llamando a $ACTUALIZAR\_PESO$ y posteriormente
pasara el subproblema recursivamente.  Al retorno evaluara si haber 
ubicado  $v$ en esa particion fue la decisión correcta.

La función $ACTUALIZAR\_PESO$ es encargada de dado un vértice y una partición
calcular cuanto incrementa el peso total de las particiones al agregarlo 
a la partición. 


\section{Orden de complejidad}
Primero vamos a analizar que pasa con la complejidad del 
algoritmo en un paso $i$ de la recursión para poder deducir 
cual sera el resultante de todas las sub llamadas que realiza el 
algoritmo. \\
En un paso $k$ de la recursion tendré $k$ vértices ubicados 
en $t$ particiones con $t <= k $ y $t<=P$. Siendo $P$ la cantidad
de particiones entre las que tengo que dividir los vértices.\\
Los $k$ vértices ubicados corresponden a que en cada paso 
de la recursión ubico un vértice en la solución recibida como 
parámetro y llamo recursivamente con esa nueva solución a ver 
que efecto tiene la decisión que tome. 
Para cada una de las $t$ particiones y en caso de 
$t<P$ serán $t+1$ tratare de ubicar los $n-k$ vértices que tengo 
disponibles en la partición seleccionada. Osea probar 
todas las combinaciones de $t$ particiones donde puedo ubicar un vértice
con los $n-k$ vértices que aun no ubique. A esto le sumo 
la posibilidad eventual de agregar una partición mas cuando
no haya llegado aun a las $P$ requeridas. \\
Por cada una de estas permutaciones haré una llamada
recursiva a un problema similar pero con 1 vértice menos
disponible y 0 o 1 partición mas que la recibida. 
Entonces la cantidad de permutaciones que tengo que evaluar en 
el paso $k$ son $(n-k) * t $ y en caso de tener aun la posibilidad 
de agregar una partición mas, seran $(n-k) * t+1 $. \\
Luego para cada permutación y antes de hacer la llamada recursiva 
deberé actualizar el resultado parcial que modifique para que internamente
en la partición donde agrego el vértice quede reflejado el cambio
de peso, en caso de producirse algún cambio. Este 
costo de actualización del peso de la partición elegida 
tendrá un costo en el peor de los casos de $n-P-1$. Que es 1 menos
el tamaño máximo en cantidad de vértices que puede tener 
una partición. Al agregar el vértice buscare ejes entre
el agregado y el resto de los vértices de la partición. \\
Contabilizando los $n$ niveles de recursión que tendrá
nuestra función el resultado global sera.\\
$\prod_{i=1}^{n-1} K(n-i)i = K^{(n-1)} \prod_{i=1}^{n-1} (n-i)i $
$= K^{(n-1)} (!(n-1))^2 $ osea $O(K^{(n-1)} (!(n-1))^2 )$

 
\section{Experimentación}
Para validar la complejidad teórica corrimos el algoritmo y tomamos los tiempos de cada corrida. Lo hicimos con casos donde la cantidades de nodos, aristas y particiones son aleatorias y acotadas.
Como el parámetro $k$ puede ser como máximo $n$ para que el algoritmo corra, optamos por reemplazarlo por este al momento de la experimentación.
En la figura \ref{fig:exacto:complejidad} se comparan los tiempos tomados con la complejidad teórica donde $x$ es la cantidad de nodos.
\ponerGrafico{graficos/exacto.pdf}{Complejidad teórica y tiempo de ejecución. Algoritmo exacto.}{1}{exacto:complejidad}